// {1} 声明一个变量追踪发现时间和完成探索时间
// 声明一个time对象，包含count属性，跟JavaScript中的方法按值或按引用传递参数有关。
// 原始数据类型是按值传递的，也就是说值的作用域只存在于函数的执行过程中。如果修改了值，只会在函数的作用域内生效。
// 如果参数以引用形式（对象）传递 ，并修改了对象中的任意属性，将会影响对象的原始值。
// 对象以引用形式传递是因为只有内存的引用被传给了函数或方法。
// 希望次数统计在算法执行过程中是全局使用的，所以需要将参数以对象传递，而不是原始值。

const Colors = {
  WHITE: 0,
  GREY: 1,
  BLACK: 2
};

/**
 * 初始化每个顶点的颜色
 * 所有顶点标记为
 * @param {*} vertices 每个顶点名字的数组
 * @returns
 */
const initializeColor = (vertices) => {
  const color = {};
  for (let i = 0; i < vertices.length; i++) {
    color[vertices[i]] = Colors.WHITE;
  }
  return color;
};

const depthFirstSearchVisit = (u, color, adjList, callback) => {
  color[u] = Colors.GREY; // 当访问顶点u时，标注其为被发现的（灰色）
  if (callback) {
    callback(u); // 如果有callback函数的话
  }
  const neighbors = adjList.get(u); // 取得包含顶点u所有邻点的列表
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i]; // {9}
    // 对于顶点u的每一个未被访问过的邻点w
    // 将调用depthFirstSearchVisit函数
    if (color[w] === Colors.WHITE) {
      depthFirstSearchVisit(w, color, adjList, callback); // 传递w和其他参数——添加顶点w入栈
    }
    color[u] = Colors.BLACK; // 在该顶点和邻点按深度访问之后，我们回退，意思是该顶点已被完全探索，并将其标注为黑色
  }
};

/**
 * 深度优先算法
 * @param {*} graph Graph类实例
 * @param {*} callback 回调函数
 */
const depthFirstSearch = (graph, callback) => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  for (let i = 0; i < vertices.length; i++) {
    // 每一个未被访问过的顶点
    if (color[vertices[i]] === Colors.WHITE) {
      // 调用私有的递归函数
      depthFirstSearchVisit(vertices[i], color, adjList, callback);
    }
  }
};

/**
 * 深度优先算法背后的思想是什么？
 * 边是从最近发现的顶点u处被向外探索的。
 * 只有连接到未发现的顶点的边被探索了。
 * 当u所有的边都被探索了，该算法回退到u被发现的地方去探索其他的边。
 * 这个过程持续到发现了所有从原始顶点能够触及的顶点。
 * 如果还留有任何其他未被发现的顶点，对新源顶点重复这个过程。
 * 重复该算法，直到图中所有的顶点都被探索了。
 */
const DFSVisit = (u, color, d, f, p, time, adjList) => {
  color[u] = Colors.GREY;
  d[u] = ++time.count; // {4} 当一个顶点第一次被发现时，追踪其发现时间
  const neighbors = adjList.get(u);
  for (let i = 0; i < neighbors.length; i++) {
    const w = neighbors[i];
    if (color[w] === Colors.WHITE) {
      p[w] = u; // {5} 当是由引自顶点u的边儿被发现的，追踪它的前溯点
      DFSVisit(w, color, d, f, p, time, adjList);
    }
  }
  color[u] = Colors.BLACK;
  f[u] = ++time.count; // {6} 当这个顶点被完全探索后，追踪其完成时间
};

const DFS = (graph) => {
  const vertices = graph.getVertices();
  const adjList = graph.getAdjList();
  const color = initializeColor(vertices);
  const d = {}; // 顶点u发现时间
  const f = {}; // 当顶点u被标注为黑色时，u的完成探索时间f[u]
  const p = {}; // 顶点u的前溯点p[u]
  // {1} 声明一个变量追踪发现时间和完成探索时间
  const time = { count: 0 };
  // {2} 声明对象d、f和p  需要为图的每一个顶点来初始化这些对象
  for (let i = 0; i < vertices.length; i++) {
    const vi = vertices[i];
    d[vi] = 0;
    f[vi] = 0;
    p[vi] = null;
  }
  for (let i = 0; i < vertices.length; i++) {
    const vi = vertices[i];
    if (color[vi] === Colors.WHITE) {
      DFSVisit(vi, color, d, f, p, time, adjList);
    }
  }
  // {3}
  return {
    discovery: d,
    finished: f,
    predecessors: p
  };
};

exports.depthFirstSearch = depthFirstSearch;
exports.DFS = DFS;
